package leetcode.code0051;

import java.util.ArrayList;
import java.util.List;

public class Solution extends Solution51 {

	private int range;
	private List<List<String>> ans;
	private String[] temp;
	private char[] chars;

	@Override
	public List<List<String>> solveNQueens(int n) {
		ans = new ArrayList<>();
		temp = new String[n];
		range = (1 << n) - 1;
		chars = new char[n];
		for (int i = 0; i < n; i++) {
			chars[i] = '.';
		}
		totalNQueens(0, 0, 0, 0);
		return ans;
	}

	public void totalNQueens(int col, int left, int right, int index) {
		if (range == col) {
			List<String> l = new ArrayList<>();
			for(String s : temp) {
				l.add(s);
			}
			ans.add(l);
			return;
		}
		int avl = range & (~(col | left | right));
		while (avl > 0) {
			int q = avl & (~avl + 1);
			avl &= avl - 1;
			temp[index] = q2str(q);
			totalNQueens(col | q, (left | q) << 1, (right | q) >>> 1, index + 1);
		}
	}

	private String q2str(int q) {
		// 0100 .Q..
		int index = (int) (Math.log(q) / Math.log(2));
		chars[index] = 'Q';
		String str = new String(chars);
		chars[index] = '.';
		return str;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		System.out.println((int) (Math.log(1) / Math.log(2)));
		int index = (int) (Math.log(4) / Math.log(2));
		System.out.println(index);
	}

}
